package q328_oddEvenList;

import CommonClass.Common.ListNode;
public class Solution_1 {
    /*
    由于只能够使用o(n)的时间复杂和o(1)的空间复杂 需要考虑原地修改
    首先使用一个count来记录一共有多少个节点 并且同时将一个指针指向最后一个节点
    用来连接偶数的节点
    count除以2也就是要移动的偶数节点 接下来只需要遍历该链表
    依次断开奇偶的连接 并且将偶数的节点连接到最后一个节点 然后最后一个节点后移即可
    当count归零 所有的节点就迁移结束
     */
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return head;

        int count = 1;
        ListNode node = head;
        while (node.next != null) {
            node = node.next;
            ++count;
        }
        ListNode start = head;
        count /= 2;
        while (count > 0) {
            ListNode temp = start.next;
            start.next = temp.next;
            temp.next = null;
            node.next = temp;
            node = node.next;
            start = start.next;
            --count;
        }

        return head;
    }
}
